Thời Lý-Trần, vùng đất bao gồm hai tỉnh Điện Biên và Lai Châu ngày nay, trước có tên là châu Ninh Viễn, sau đổi là châu Mường Lễ. Theo sách Hưng Hóa phong thổ lục của Tiến sĩ Hoàng Trọng Chính, soạn năm 1778, thì họ Đèo ở châu Mường Lễ đời này qua đời khác luôn được nhà cầm quyền nước Việt cho cai quản miền đất biên cương này.

Năm 1407, quân Minh sang xâm lược Đại Việt, Đèo Cát Hãn khi ấy đang đứng đầu châu Mường Lễ, liền theo nhà Minh để được tiếp tục giữ ngôi vị.

Năm 1416, Lê Lợi (1385-1433)[1] tổ chức hội thề ở Lũng Nhai, rồi phất cờ khởi nghĩa năm 1418, tự xưng là Bình Định vương.

Sau khi tiêu diệt viện binh chủ lực của quân Minh và bao vây thành Đông Quan (nay là Hà Nội) tháng 11 năm 1427, Lê Lợi đã phái Chủ thư thị sử là Trần Hổ đi châu Mường Lễ, chiêu dụ Đèo Cát Hãn. Viên thổ quan này đồng ý quy thuận, nên vẫn được tiếp tục cai quản vùng đất trên.

Sau mười năm chiến đấu gian khổ (1418 - 1428), Lê Lợi và nghĩa quân Lam Sơn đã giành được thắng lợi hoàn toàn. Năm 1428, Lê Lợi lên ngôi, lấy niên hiệu là Thuận Thiên, và tự xưng mình là Lam Sơn động chủ, Ngọc Hoa động chủ.

Lê Thái Tổ (tức Lê Lợi) ở ngôi được khoảng ba năm thì Đèo Cát Hãn ngầm liên kết với Kha Đốn (hay Kha Lại, là một viên quan đang khởi binh kình chống vua Ai Lao), đánh chiếm vùng đất Mường Muỗi (hay Mường Mỗi, nay là Thuận Châu thuộc Sơn La).

Hiểu được tầm quan trọng của miền Tây Bắc đối với lãnh thổ và sự an nguy của đất nước, theo Đại Việt thông sử của Lê Quý Đôn, thì:

Tháng 12 năm Tân Hợi (1431),... vua bèn sai Tư đồ Lê Sát và Quốc vương Tư Tề dẫn quân [đi] đánh [Mường Lễ], rồi vua lại thân chinh.Năm Nhâm Tý (1432), mùa xuân tháng Giêng, quan quân đánh được Mường Lễ, Kha Lại bị giết, Đèo Cát Hãn chạy trốn, quan quân bắt hết dư đảng, bèn đổi Mường Lễ làm Phục Lễ. Ngày 3 tháng 3, vua kéo quân trở về... Tháng 11, Cát Hãn và con là Mạnh Vượng xin hàng, được nhà vua tha tội. Khi Cát Hãn tới kinh tạ tội, được phong chức Tư mã...[2]

Sau khi bình định xong, trên đường đại quân hồi kinh, Lê Lợi có làm hai bài thơ: một, cho khắc trên vách núi Pú Huổi Chỏ (bên tả ngạn sông Đà, thuộc Mường Lệ nay thuộc xã Lê Lợi, huyện Sìn Hồ, tỉnh Lai Châu); hai, cho khắc trên vách đá Hào Tráng (gần Chợ Bờ, huyện Đà Bắc, tỉnh Hòa Bình ngày nay).